package com.wuyou.simple;

/**
 * 3258. 统计满足 K 约束的子字符串数量 I
 *
 * @Date 2024/11/12 10:41
 * @Author 无忧
 */
public class CountKConstraintSubstrings {

    public static void main(String[] args) {
        String[] s = {"10101", "11111", "10101"};
        int[] k = {1, 1, 1};
        for (int i = 0; i < s.length; i++) {
            System.out.println("第" + (i + 1) + "结果—> " + sol_2(s[i], k[i]));
        }
    }


    public static int sol_2(String s, int k) {
        int res = 0, length = s.length(), l = 0, count_0 = 0, count_1 = 0;
        char[] chars = s.toCharArray();

        for (int r = 0; r < length; r++) {
            if (chars[r] == '0') {
                count_0++;
            } else {
                count_1++;
            }

            // 当count_0或count_1超过k时，移动左指针以缩小窗口
            while (count_0 > k && count_1 > k) {
                if (chars[l] == '0') {
                    count_0--;
                } else {
                    count_1--;
                }
                l++;
            }

            // 计算以r为右边界的满足条件的子串数量
            res += r - l + 1;
        }
        return res;
    }

    /**
     * 给你一个 二进制 字符串 s 和一个整数 k。
     * 如果一个 二进制字符串 满足以下'任一'条件，则认为该字符串满足 k 约束：
     * 字符串中 0 的数量最多为 k。
     * 字符串中 1 的数量最多为 k。
     * 返回一个整数，表示 s 的所有满足 k 约束的子字符串的数量。
     * 滑动窗口：又边界为count_0<=k || count_1<=k
     *
     * @param s
     * @param k
     * @return
     */
    public static int sol_1(String s, int k) {
        int res = 0, length = s.length();
        char[] chars = s.toCharArray();
        for (int i = 0; i < length; i++) {
            int j = i, count_0 = 0, count_1 = 0;
            StringBuilder sb = new StringBuilder();
            while (j < length && (count_0 <= k || count_1 <= k)) {
                if (chars[j] == '0') {
                    count_0++;
                } else {
                    count_1++;
                }
                if (count_0 > k && count_1 > k) {
                    break;
                }
                sb.append(chars[j]);
                res++;
                j++;
            }
        }
        return res;
    }
}
